// https://www.lintcode.com/problem/reverse-words-in-a-string-iii/

public class Solution {
    /**
     * @param s: a string
     * @return: reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order
     */
    public String reverseWords(String s) {
        // Write your code here
        StringBuilder sb = new StringBuilder(s);
        boolean isSpace = true;
        int i = 0, start = 0;
        while (i < s.length()) {
            if (s.charAt(i) == ' ') {
                if (!isSpace) { // 上一个字符不为空格
                    reverse(sb, start, i - 1);
                    isSpace = true;
                }
            } else {
                if (isSpace) {
                    start = i;
                    isSpace = false;
                }
            }
            ++i;
        }
        if (!isSpace) {
            reverse(sb, start, i - 1);
        }
        return sb.toString();
    }
    
    protected void reverse(StringBuilder sb, int start, int end) {
        while (start < end) {
            Character  cs = sb.charAt(start), ce = sb.charAt(end);
            sb.setCharAt(start, ce);
            sb.setCharAt(end, cs);
            ++start;
            --end;
        }
    }
}